package Leetcode.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/9/7 17:26
 * @Description:
 * 给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，
 * 其中 roads[i] = [ai, bi, distance i] 表示城市 ai 和 bi 之间有一条 双向 道路，道路距离为 distance i 。
 * 城市构成的图不一定是连通的。
 *
 * 两个城市之间一条路径的 分数 定义为这条路径中道路的 最小 距离。
 *
 * 城市 1 和城市 n 之间的所有路径的 最小 分数。
 *
 * 注意：
 *
 * 一条路径指的是两个城市之间的道路序列。
 * 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
 * 测试数据保证城市 1 和城市n 之间 至少 有一条路径。
 *
 * 输入：n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
 * 输出：5
 * 解释：城市 1 到城市 4 的路径中，分数最小的一条为：1 -> 2 -> 4 。这条路径的分数是 min(9,5) = 5 。
 * 不存在分数更小的路径。
 * 示例 2：
 * 输入：n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
 * 输出：2
 * 解释：城市 1 到城市 4 分数最小的路径是：1 -> 2 -> 1 -> 3 -> 4 。这条路径的分数是 min(2,2,4,7) = 2 。
 */

public class 两个城市间路径的最小分数 {
    //得用全局变量，不然不能修改ans传递函数
    int ans = Integer.MAX_VALUE;
    /**
     *  带权无向图
     *  因为题目可以允许折返，其本质就是找一个能够到达n的连通图（题目已经保证能够到达n）
     *  即找该连通图中最小的权值即可，min保存
     *
     *  最开始还复杂化了，以为得回溯才能实现= =
     * @param n n个城市
     * @param roads    roads[i] = [ai, bi, distance i] 表示城市 ai 和 bi 之间有一条 双向 道路，
     *                 道路距离为 distance i 。城市构成的图不一定是连通的。
     * @return  两个城市之间一条路径的 分数 定义为这条路径中道路的 最小 距离。
     */
    public int minScore(int n, int[][] roads) {
        List<int[]>[] graph = new ArrayList[n + 5];
        Arrays.setAll(graph,value ->  new ArrayList<>());

        boolean[] visited = new boolean[n + 1];
        for (int[] e : roads) {
            graph[e[0]].add(new int[]{e[1], e[2]});
            graph[e[1]].add(new int[]{e[0], e[2]});
        }

        dfs(graph, visited, 1);
        return ans;
    }

    private void dfs(List<int[]>[] graph, boolean[] visited,  int i) {
        visited[i] = true;
        for (int[] vertex : graph[i]) {
            int v = vertex[0], weight = vertex[1];
            ans = Math.min(ans, weight);
            if (!visited[v]) {
                dfs(graph, visited,  v);
            }
        }
    }
}
